(a) Field of the Invention
The present invention relates to a high-speed and large volume crossbar switch and an arbitration method for sending cells through the switch. More specifically, the present invention relates to a method for connecting L2-numbered n×n crossbar switches to configure an N×N switch when n is a divisor of N and L=N/n, a device for transmitting cells to an output port from an input port, and an arbitration method thereof.
(b) Description of the Related Art
Since it is required to send a maximum of N cells through a predetermined output port at a single time slot in the case of an N×N output-queued switch, the operation rate of the switch and a memory must be N times faster than an input line rate. The reason that the output-queued switch is not applied to high-speed switches even though it has 100% throughput for uniform traffic and excellent features in terms of QoS support, is mainly due to the above-noted speedup problem.
Since the operation rate of the switch and the memory is the same as the input line rate in the case of an input-queued switch, the input-queued switches are applied to most of the high-speed switches. However, the structure of the high-speed input-queued switch has a VOQ (virtual output queue) form for solving the head-of-line blocking problem in the case of an input port, and it generally has a crossbar form that is a non-blocking high-speed switch in the case of a switch. Various arbitration methods for solving the contention problem between the input and output ports in the input-queued switch, and providing 100% throughput, have recently been proposed.
Among the-above described algorithms are the PIM (parallel iterative matching) method (refer to U.S. Pat. No. 5,267,235), the 2DRR (Two-dimensional round robin matching) method (refer to U.S. Pat. No. 5,299,190), the iSLIP method (refer to U.S. Pat. No. 5,500,858), and the dual round robin matching method (refer to “Centralized contention resolution schemes for a large-capacity optical ATM switch” by H. J. Chao and J-S Park, Proc. IEEE ATM Workshop97, Fairfax, Va., pp.10-11, May 1998). The algorithms allow 100% throughput, but they are limited by arbitration time as the number of the input/output ports increases, and hence, it is not advantageous to apply them to the large-volume and high-speed switches.
For example, the most commercialized iSLIP method has been mainly applied to switches with less than 32 ports. Since a tera-level switch with a 2.5 Gbps port rate needs a 512×512 crossbar switch, it causes a fundamental problem in use of a single crossbar switch and the conventional arbitration method to thus configure the switch.
Expandable switching solutions proposed as huge switching solutions include a channel group switching solution on the distribution network basis (refer to U.S. Pat. No. 5,724,351), and a crossbar switching solution in the Clos network format (refer to “Low-cost scalable switching solutions for broadband networking: The Atlanta architecture and chipset” by F. M. Chiussi, J. G. Kneuer, and V. P. Kumar, IEEE Commun. Mag., pp.44-53, December 1997). The channel group switching method advantageously uses small-capacity group switches to configure a large-capacity switch, but if the number of input/output ports increase, it becomes very complicated to design a distribution network, and accordingly, it is difficult to configure a large-capacity switch.
In the case of the crossbar switch of the Clos network type, since a plurality of paths are provided between the input/output ports, a complex scheduling method for distributing the loads of traffic per path is required, and when the number of high-speed input/output ports increases, high-speed crossbar switches are proportionally needed, therefore, causing difficulties in configuring a large-capacity switch.